None
Not Applicable
The present invention is related to the field of Asynchronous Transfer Mode (ATM) networks, and more specifically to the use of a Virtual Connection Parameter Table (VCPT) in an ATM switch in which operational parameters are stored on a per-connection basis.
During the operation of an ATM switch, it is necessary for the switch to perform specific actions in response to receiving a cell at a given input or ingress port. Most notably, the switch must forward the cell to the correct output or egress port. The switch typically performs a variety of other functions as well, such as for example monitoring subscriber data rates to enforce a maximum subscribed rate, and collecting various statistics of network operation to be used by network management software.
For many functions, it is necessary for the switch to store sets of parameters, each set being associated with a given connection. For example, the switch may employ an internal connection identifier (CID) used by components within the switch to forward a cell to the correct egress port. Other per-connection parameters can include such things as a maximum allowed data rate for a connection, and one or more counters used to track some aspect of the connection""s operation, such as cell error rate.
The network-wide connections in an ATM are referred to as xe2x80x9cvirtualxe2x80x9d connections. There are two broad classes of virtual connections: xe2x80x9cvirtual path connectionsxe2x80x9d or VPCs, and xe2x80x9cvirtual channel connectionsxe2x80x9d or VCCs. VPCs in ATM are specified by an 8-bit field appearing in an ATM cell called the Virtual Path Identifier (VPI). There may be several channels within a VPC; these are specified by a separate 16-bit field called the Virtual Channel Identifier (VCI). All of the channels within a VPC share some operational parameters, including the CID used for forwarding the cells within the switch. The other type of connection, the VCC, is specified by both a VPI and a VCI. In general, there may be multiple VCCs using the same VPI value. The group of VCCs having a given VPI are referred to herein as the xe2x80x9csetxe2x80x9d of VCCs for that VPI. Different VCCs generally employ different parameters within a switch, including VCCs in the same set.
In order to create the desired association between VPIs/VCIs and their associated parameters within a switch, a table is used that is indexed in some fashion by VPI and VCI values. When a cell arrives at a port, the VPI and VCI from the cell are used to look up the parameters in the table. In the description below, such a table is referred to as a xe2x80x9cvirtual connection parameter tablexe2x80x9d or VCPT. A VCPT resides on each line card within a switch, so that it may be accessed quickly and efficiently upon the arrival of a cell at a line card port. The VCPT can be shared among multiple ports on a line card. If that is done, a port identifier is also used as part of the index into the VCPT to distinguish connections having the same VPI and VCI values but appearing on different ports.
As mentioned above, the channels within a given VPC use a common set of parameters. Thus for each VPC on a port only one entry in the VCPT is needed, and this entry can be indexed by the corresponding VPI value alone. Each VCC also requires an entry, which means that for a given VPI there will be a set of VCPT entries, each entry corresponding to a different VCC within the set as identified by the VCI. The maximum number of VCCs in a set that share a given VPI is variable depending on network configuration. VCC set sizes are specified on a per-port and per-VPI basis by specifying the maximum number of VCI bits that may be used to identify a VCC within the set. Thus for example the maximum number of VCI bits may be specified as 10, which corresponds to a net size of 1024 VCCs. Because the number of VCCs within a set is variable, the number of entries that may be needed in the VCPT for a given set of VCCs is also variable. Thus the VCPT must be configured and accessed in a manner that accommodates the differences between VPCs and VCCs, and also accommodates the variability of the sizes of the VCC sets,
Conceptually the VCPT could be directly addressed by concatenating the port identifier and the VPI and VCI from a received cell. Among other impracticalities, such a scheme would be very wasteful of memory, because (1) typically not every VPI and VCI are in active use at a given time on a port, and (2) for VPCs, only one of the block of locations covered by each VPI would be needed. Therefore it would be preferable for the VCPT to be structured so that its storage capacity can be assigned flexibly and re-assigned dynamically in response to the creation and deletion of network connections.
One problem that can arise in dynamic re-assignment schemes is fragmentation of storage space, in which allocated areas are separated by xe2x80x9cholesxe2x80x9d, or empty locations that result from the deletion of connections. If fragmentation is not managed properly, the effective storage capacity of the table may be reduced dramatically, resulting in a reduction in the maximum number of active connections that a switch can handle.
It is desirable to minimize performance-reducing effects such as fragmentation of the VCPT. In general, it is desirable for VCPT space to be allocated and de-allocated in a manner that makes efficient use of VCPT storage capacity, so that the ability of the switch to respond to demand for connections is maximized.
In accordance with the present invention, a technique is disclosed for managing free space in a virtual connection parameter table (VCPT) that enables the flexible assignment of storage capacity to either VPCs or sets of VCCs. For VCCs, VCPT locations are allocated in variable-sized xe2x80x9cchunksxe2x80x9d. Storage efficiency is enhanced by tailoring the size of each allocated chunk to the configured maximum number of VCCs in a set, rather than to the absolute maximum number (216) of VCCs which in practice might seldom or never be used. Also, VCPT locations that become empty as a result of the deletion of connections are reused and/or recycled into larger chunks in a manner that reduces any tendency of the VCPT toward fragmentation.
In the disclosed technique, a VCC pointer and a VPC pointer are maintained which respectively define VCC and VPC areas at opposite ends of the VCPT. The VCC and VPC areas expand into the central area of the VCPT as the pointers are advanced. A number of xe2x80x9cfree listsxe2x80x9d are used to hold the addresses of either single locations (for VPCs) or chunks of locations (for sets of VCCs) that have been de-allocated and are available for re-allocation. There are different free lists for different VCC set sizes that can be configured, i.e., for sets configured to use different maximum numbers of VCI bits. In one embodiment there are separate free lists for set sizes of all powers of 2 between 64 and 16K.
When a new VPC is created, so that a corresponding VPC entry in the VCPT is required, it is first determined whether the VPC free list contains an entry, and if so the VCPT location identified by the entry is allocated as a VPC entry to hold parameters for the new VPC. If the VPC free list does not contain an entry, it is determined whether the VPC pointer can be advanced to expand the VPC area into the central area of the VCPT. If so, the VPC pointer is advanced and a location in the expanded part of the VPC area is allocated. De-allocation of a VPC entry proceeds in reverse order, i.e., if possible the VPC area is shrunk by backing up the VPC pointer, and if not the entry is placed on the VPC free list to be available for a subsequent allocation.
When a new VCC is created, an allocation process similar to the VPC allocation process is carried out if the new VCC is the first VCC being created for a given port and VPI. For each allocation, the appropriate VCC free list is used based on the configured set size. For example, if a given port and VPI are configured to have VCCs identified by 10 bits, an allocation chunk size of 1024 is required. When the VCC pointer is advanced, it advances by an amount sufficient to claim the required-size chunk. As with VPC entries, de-allocation of VCC entries proceeds in reverse order. De-allocated chunks are preferably removed from the VCC area by backing up the VCC pointer, but if that is not possible then the chunks are placed on the appropriate free list.
A consolidation technique is also disclosed that contributes to efficient reuse of de-allocated VCPT entries. The consolidation process is performed whenever a VCC chunk is de-allocated. When possible, the process further backs up the VCC pointer in order to maximize the space available in the central area of the VCPT. The process also combines pairs of entries on the free lists in order to create larger-sized chunks. During subsequent allocations, a combined chunk may be allocated in whole to a same-size set of VCCs, or may be split into smaller chunks and allocated to multiple smaller-sized VCC sets. This technique enhances flexibility and efficiency in the allocation process.
Other aspects, features, and advantages of the present invention are disclosed in the detailed description which follows.